﻿#pragma once
#include "yzrutil.h"
#include "Iterator.hpp"
#include "List.hpp"
#include "ListIterator.hpp"
#include "lang/Exception.h"
#include "util/Util.h"
#include <optional>

namespace yzrilyzr_collection{
	//template<typename E>

	template<typename E>
	ECLASS(LinkedList, public List<E>){
		class Node{
			public:
			E item;
			Node * next;
			Node * prev;
			Node(Node * prev, const E & item, Node * next) :
				prev(prev),
				item(item),
				next(next){}
		};
	public:
	LinkedList(){}
	LinkedList(const std::initializer_list<E> &init) :LinkedList(init.begin(), init.size()){}

	LinkedList(const yzrilyzr_array::Array<E> &array) :LinkedList(array._array, array.length){}

	LinkedList(const E * array, u_index length){
		for(u_index i=0;i < length;i++){
			add(array[i]);
		}
	}
	void linkLast(const E & e){
		Node * l=last;
		Node * newNode=new Node(l, e, nullptr);
		last=newNode;
		if(l == nullptr)
			first=newNode;
		else
			l->next=newNode;
		size1++;
		this->modCount++;
	}
	void linkBefore(const E & e, Node * succ){
		Node * pred=succ->prev;
		Node * newNode=new Node(pred, e, succ);
		succ->prev=newNode;
		if(pred == nullptr)
			first=newNode;
		else
			pred->next=newNode;
		size1++;
		this->modCount++;
	}
	bool add(const E & e)override{
		linkLast(e);
		return true;
	}

	u_index size() const override{
		return size1;
	}

	void add(u_index index, const E & element)override{
		yzrilyzr_util::Util::checkIndex(index, size1);
		if(index == size1)
			linkLast(element);
		else
			linkBefore(element, node(index));
	}
	E set(u_index index, const E & element)override{
		yzrilyzr_util::Util::checkIndex(index, size1);
		Node * x=node(index);
		E oldVal=x->item;
		x->item=element;
		return oldVal;
	}
	bool isEmpty() const override{
		return size() == 0;
	}

	E get(u_index index) const override{
		return node(index)->item;
	}

	E & operator[](u_index index) const override{
		return node(index)->item;
	}

	void clear() override{
		for(Node * x=first; x != nullptr;){
			Node * next=x->next;
			delete x;
			x=next;
		}
		first=last=nullptr;
		size1=0;
		this->modCount++;
	}

	std::optional<E> poll(){
		Node * f=first;
		if(f == nullptr)return std::nullopt;
		return unlinkFirst(f);
	}
	u_index size1=0;
	Node * first=nullptr;
	Node * last=nullptr;

	E unlinkFirst(Node * f){
		// assert f == first && f != nullptr;
		E element=std::move(f->item);
		Node * next=f->next;
		delete f;
		first=next;
		if(next == nullptr)
			last=nullptr;
		else
			next->prev=nullptr;
		size1--;
		this->modCount++;
		return element;
	}

	Node * node(u_index index) const{
		if(index < (size1 >> 1)){
			Node * x=first;
			for(u_index i=0; i < index; i++)
				x=x->next;
			return x;
		} else{
			Node * x=last;
			for(u_index i=size1 - 1; i > index; i--)
				x=x->prev;
			return x;
		}
		return nullptr;
	}
	bool remove(const E & e)override{
		for(Node * x=first; x != nullptr; x=x->next){
			if(e == x->item){
				unlink(x);
				return true;
			}
		}
		return false;
	}
	E remove(u_index index) override{
		return unlink(node(index));
	}

	E unlink(Node * x){
		// assert x != nullptr;
		E element=std::move(x->item);
		Node * next=x->next;
		Node * prev=x->prev;
		if(prev == nullptr){
			first=next;
		} else{
			prev->next=next;
			x->prev=nullptr;
		}
		if(next == nullptr){
			last=prev;
		} else{
			next->prev=prev;
			x->next=nullptr;
		}
		delete x;
		size1--;
		this->modCount++;
		return element;
	}
	//template<typename E>
	ECLASS(LinkIterator, public ListIterator<E>){
			protected:
			const LinkedList * clist=nullptr;
			LinkedList * list=nullptr;
			Node * lastReturned=nullptr;
			Node * nextNode=nullptr;
			u_index nextIndex1;
			u_index expectedModCount;
			public:
			LinkIterator(const LinkedList * clist, LinkedList * list) : clist(clist), list(list), expectedModCount(clist->modCount){
				u_index index=0;
				nextNode=(index == clist->size())?nullptr:clist->node(index);
				nextIndex1=index;
			}

			bool hasNext()const override{
				return nextIndex1 < (clist->size());
			}

			E & next()override{
				checkForComodification();
				if(!hasNext())
					throw yzrilyzr_lang::NoSuchElementException();
				lastReturned=nextNode;
				nextNode=nextNode->next;
				nextIndex1++;
				return lastReturned->item;
			}

			void checkForComodification(){
				if(clist->modCount != expectedModCount)
					throw yzrilyzr_lang::ConcurrentModificationException();
			}

			bool hasPrevious()const override{
				return nextIndex1 > 0;
			}

			E & previous()override{
				checkForComodification();
				if(!hasPrevious())
					throw yzrilyzr_lang::NoSuchElementException();
				lastReturned=nextNode=(nextNode == nullptr)?clist->last:nextNode->prev;
				nextIndex1--;
				return lastReturned->item;
			}

			u_index nextIndex()const override{
				return nextIndex1;
			}

			u_index previousIndex()const override{
				return nextIndex1 - 1;
			}
			void remove() override{
				checkForComodification();
				if(lastReturned == nullptr)
					throw yzrilyzr_lang::IllegalStateException();
				Node * lastNext=lastReturned->next;
				list->unlink(lastReturned);
				if(nextNode == lastReturned)
					nextNode=lastNext;
				else
					nextIndex1--;
				delete lastReturned;
				lastReturned=nullptr;
				expectedModCount++;
			}

			void set(E & e)override{
				if(lastReturned == nullptr)
					throw yzrilyzr_lang::IllegalStateException();
				checkForComodification();
				lastReturned->item=e;
			}

			void add(E & e)override{
				checkForComodification();
				lastReturned=nullptr;
				if(nextNode == nullptr)
					list->linkLast(e);
				else
					list->linkBefore(e, nextNode);
				nextIndex1++;
				expectedModCount++;
			}
	};
	std::unique_ptr<Iterator<E>> iterator() override{
		return std::make_unique<LinkIterator>(this, this);
	}
	std::unique_ptr<Iterator<E>> constIterator()const override{
		return std::make_unique<LinkIterator>(this, nullptr);
	}
	};
}